o/********************************************************************************** 
* 
* Given two words (start and end), and a dictionary, find all shortest transformation 
* sequence(s) from start to end, such that:
* 
* Only one letter can be changed at a time
* Each intermediate word must exist in the dictionary
* 
* For example,
* 
* Given:
* start = "hit"
* end = "cog"
* dict = ["hot","dot","dog","lot","log"]
* 
* Return
* 
*   [
*     ["hit","hot","dot","dog","cog"],
*     ["hit","hot","lot","log","cog"]
*   ]
* 
* Note:
* 
* All words have the same length.
* All words contain only lowercase alphabetic characters.
* 
*               
**********************************************************************************/


class Solution
{
public:
  vector< vector<string> > 
  findLadders(string start, string end, unordered_set<string> &dict)
  {
    vector< vector<string> > ladders;
    vector<string> ladder;

    ladder.push_back(start);

    if (start == end)
      {
        ladder.push_back(end);
        ladders.push_back(ladder);
        return ladders;
      }

    map< string, unordered_set<string> >& parents = buildTree(start, end, dict);
    if (parents.size() <= 0)
      {return ladders;}
    
    generatePath(start, end, parents, ladder, ladders);

    return ladders;
    
  }

private:

  map< string, unordered_set<string> >&
  buildTree(string start, string end, unordered_set<string> &dict)
  {
    static map< string, unordered_set<string> > parents;
    parents.clear();

    unordered_set<string> levels[3];
    unordered_set<string> *previousLevel = &levels[0];
    unordered_set<string> *currentLevel  = &levels[1];
    unordered_set<string> *nextLevel     = &levels[2];
    unordered_set<string> *p = NULL;
    
    currentLevel->insert(start);
    bool reachEnd = false;

    while ( !reachEnd )
      {
        nextLevel->clear();
        for (auto it = currentLevel->begin(); it != currentLevel->end(); it++)
          {
            for (int i = 0; i < it->size(); i++)
              {
                string newWord = *it;
                for (char c = 'a'; c <= 'z'; c++)
                  {
                    newWord[i] = c;
                    if ( newWord == end )
                      {
                        reachEnd = true;
                        parents[*it].insert(newWord);
                        continue;
                      }

                    if ( dict.count(newWord) == 0 || currentLevel.count(newWord) > 0 || previousLevel.count(newWord) > 0 )
                      { continue; }

                    nextLevel->insert(newWord);
                    parents[*it].insert(newWord);
                  }
              }
          }

        if (nextLevel->empty())
          {break;}
        
        p = previousLevel;
        previousLevel = currentLevel;
        currentLevel = nextLevel;
        nextLevel = p;
                     
      }//while

    if ( !reachEnd )
      { parents.clear(); }
    
    return parents;
    
  }

  void generatePath(string start, string end,
                    map< string, unordered_set<string> > &parents,
                    vector<string> ladder,
                    vector< vector<string> > ladders)
  {
    if ( parents.find(start) == parents.end() )
      {
        if(start == end)
          {
            //ladder.push_back(start);
            ladders.push_back(ladder);
            
          }
        return;
      }

    for(auto it = parents[start].begin(); it != parents[start].end(); it++)
      {
        ladder.push_back(*it);
        generatePath(it, end, parents, ladder, ladders);
        ladder.pop_back();
      }
    
  }

  
};
